#pragma once
#include <initializer_list>
#include <iterator>
#include <type_traits>

struct Node_base
{
    Node_base *succ = nullptr;
    void insert_after(Node_base *n);
    void insert_after(Node_base *first, Node_base *last);
    void erase_after();
};

void Node_base::insert_after(Node_base *n)
{
    n->succ = succ;
    succ = n;
}

void Node_base::insert_after(Node_base *first, Node_base *last)
{
    auto tmp = first->succ;
    if (last)
    {
        first->succ = last->succ;
        last->succ = succ;
    }
    else
    {
        first->succ = nullptr;
    }
    succ = tmp;
}

void Node_base::erase_after()
{
    succ = succ->succ;
}

template <class T>
struct Link : public Node_base
{
    T val;
    explicit Link(const T &v = T()) : Node_base{}, val(v) {}
};
template <class T>
struct Slist_iterator
{
    using iterator_category = std ::forward_iterator_tag;
    using value_type = T;
    using difference_type = ptrdiff_t;
    using pointer = T *;
    using reference = T &;
    explicit Slist_iterator(Node_base *p = nullptr) : node(p) {}
    reference operator*() const { return static_cast<Link<T> *>(node)->val; }
    pointer operator->() const { return &static_cast<Link<T> *>(node)->val; }
    bool operator==(const Slist_iterator &b) const { return node == b.node; }
    bool operator!=(const Slist_iterator &b) const { return node != b.node; }
    operator bool() const
    {
        return node != nullptr;
    }
    Node_base *node;
};

template <class T>
struct Slist_const_iterator
{
    using iterator_category = std::forward_iterator_tag;
    using value_type = T;
    using difference_type = ptrdiff_t;
    using pointer = const T *;
    using reference = const T &;

    explicit Slist_const_iterator(const Node_base *p = nullptr) : node(p) {}
    Slist_const_iterator &operator++()
    {
        node = node->succ;
        return *this;
    }
    reference operator*() const { return static_cast<const Link<T> *>(node)->val; }
    pointer operator->() const { return &static_cast<const Link<T> *>(node)->val; }
    bool operator==(const Slist_const_iterator &b) const { return node == b.node; }
    bool operator!=(const Slist_const_iterator &b) const { return node != b.node; }
    operator bool() const
    {
        return node != nullptr;
    }
    const Node_base *node;
};

template <class Iter, class Tag>
using is_iterator = std::is_convertible<typename std::iterator_traits<Iter>::iterator_category, Tag>;
template <class Iter>
using is_input_iterator = is_iterator<Iter, std::input_iterator_tag>;

template <class T>
class slist
{
public:
    using size_type = size_t;
    using value_type = T;
    using iterator = Slist_iterator<T>;
    using const_iterator = Slist_const_iterator<T>;
    slist() = default;
    explicit slist(size_type n, const T &val = T())
    {
        for (auto p = &head; n; --n, p = p->succ)
        {
            p->succ = new Link<T>(val);
        }
    }
    template <class InputIt, class = std::enable_if<is_input_iterator<InputIt>::value>>
    slist(InputIt first, InputIt last)
    {
        for (auto p = &head; first != last; ++first, p = p->succ)
        {
            p->succ = new Link<T>(*first);
        }
    }
    slist(std::initializer_list<T> lst) : slist(lst.begin(), lst.end()) {}
    slist(const slist &l) : slist(l.begin(), l.end()) {}
    slist &operator=(const slist &l)
    {
        if (this != &l)
            assign(l.begin(), l.end());
        return *this;
    }
    slist(slist &&l) noexcept : head(l.head) { l.head.succ = nullptr; }
    slist &operator=(slist &&l) noexcept
    {
        clear();
        head.succ = l.head.succ;
        l.head.succ = nullptr;
        return *this;
    }
    ~slist() { clear(); }
    iterator before_begin() { return iterator(&head); }
    const_iterator before_begin() const { return const_iterator(&head); }
    iterator begin() { return iterator(head.succ); }
    const_iterator begin() const { return const_iterator(head.succ); }
    iterator end() { return iterator(nullptr); }
    const_iterator end() const { return iterator(nullptr); }
    iterator insert_after(iterator p, const T &v);
    iterator insert_after(iterator p, size_type n, const T &val);
    template <class InputIt, class = std::enable_if<is_input_iterator<InputIt>::value>>
    iterator insert_after(iterator p, InputIt first, InputIt last);
    iterator erase_after(iterator p);
    iterator erase_after(iterator first, iterator last);
    void clear();
    void assign(size_type n, const T &val);

    template <class InputIt, class = std::enable_if<is_input_iterator<InputIt>::value>>
    void assign(InputIt first, InputIt last);
    void push_front(const T &v) { insert_after(before_begin(), v); }
    void pop_front() { erase_after(before_begin()); }
    T &front() { return *begin(); }
    bool empty() const { return head.succ == nullptr; }
    void splice_after(iterator p, slist &l) { splice_after(p, l, l.before_begin(), l.end()); }
    void splice_after(iterator p, slist &l, iterator first, iterator last) { _splice_after(p, first, last); }

private:
    iterator _splice_after(iterator p, iterator first, iterator last);
    Node_base head;
};
template <class T>
typename slist<T>::iterator slist<T>::insert_after(iterator p, const T &v)
{
    auto tmp = new Link<T>(v);
    p.node->insert_after(tmp);
    return iterator(tmp);
}

template <class T>
typename slist<T>::iterator slist<T>::insert_after(iterator p, slist::size_type n, const T &val)
{
    if (n == 0)
        return p;
    slist tmp(n, val);
    return _splice_after(p, tmp.before_begin(), tmp.end());
}

template <class T>
template <class InputIt, class>
typename slist<T>::iterator slist<T>::insert_after(iterator p, InputIt first, InputIt last)
{
    if (first == last)
        return p;
    slist<T> tmp(first, last);
    return _splice_after(p, tmp.before_begin(), tmp.end());
}
template <class T>
typename slist<T>::iterator slist<T>::erase_after(iterator p)
{
    auto next = p.node->succ;
    p.node->erase_after();
    delete static_cast<Link<T> *>(next);
    return iterator(p.node->succ);
}
template <class T>
typename slist<T>::iterator slist<T>::erase_after(iterator first, iterator last)
{
    while (first.node->succ != last.node)
    {
        erase_after(first);
    }
    return last;
}
template <class T>
void slist<T>::clear()
{
    iterator pos = iterator(&head);
    while (pos)
    {
        pos = erase_after(pos);
    }
}
template <class T>
void slist<T>::assign(slist::size_type n, const T &val)
{
    iterator prev = before_begin(), curr = begin(), end_ = end();
    for (; curr != end_ && n > 0; ++prev, ++curr, --n)
    {
        *curr = val;
    }
    if (n > 0)
    {
        insert_after(prev, n, val);
    }
    else if (curr != end_)
    {
        erase_after(prev, end_);
    }
}
template <class T>
template <class InputIt, class>
void slist<T>::assign(InputIt first, InputIt last)
{
    iterator prev = before_begin(), curr = begin(), end_ = end();
    for (; curr != end_ && first != last; ++prev, ++curr, ++first)
    {
        *curr = *first;
    }
    if (first != last)
    {
        insert_after(first, last);
    }
    else if (curr != end_)
    {
        erase_after(prev, end_);
    }
}
template <class T>
typename slist<T>::iterator slist<T>::_splice_after(iterator p, iterator first, iterator last)
{
    Node_base *e = first.node;
    while (e->succ != last.node)
        e = e->succ;
    if (first.node == e)
        return iterator(p);
    p.node->insert_after(first.node, e);
    return iterator(e);
}